package main

import "fmt"

/*
链表排序
给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]
*/

type ListNode struct {
	Val  int
	Next *ListNode
}

/*
自底向上归并排序
使用自底向上的方法实现归并排序，则可以达到o(1)的空间复杂度。
首先求得链表的长度length，然后将链表拆分成子链表进行合并。

具体做法如下。
1.用 subLength表示每次需要排序的子链表的长度，初始时 subLength=1.
2.每次将链表拆分成若干个长度为subLength 的子链表（最后一个子链表的长度可以小于subLength），按照每两个子链表一组进行合并，
合并后即可得到若干个长度为subLength×2 的有序子链表（最后一个子链表的长度可以小于subLength×2)。
3.将subLength的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于length，整个链表排序完毕。

如何保证每次合并之后得到的子链表都是有序的呢？可以通过数学归纳法证明。
初始时subLength=1，每个长度为 1的子链表都是有序的。
如果每个长度为subLength 的子链表已经有序，合并两个长度为subLength 的有序子链表，得到长度为subLength×2 的子链表，一定也是有序的。
当最后一个子链表的长度小于subLength 时，该子链表也是有序的，合并两个有序子链表之后得到的子链表一定也是有序的。
*/

func merge(head1, head2 *ListNode) *ListNode {
	//创建头节点为0的新链表
	dummyHead := &ListNode{}
	//创建全空的新链表
	//var dummyHead *ListNode
	t, t1, t2 := dummyHead, head1, head2
	for t1 != nil && t2 != nil {
		if t1.Val <= t2.Val {
			t.Next = t1
			t1 = t1.Next
		} else {
			t.Next = t2
			t2 = t2.Next
		}
		t = t.Next
	}
	if t1 != nil {
		t.Next = t1
	} else if t2 != nil {
		t.Next = t2
	}
	return dummyHead.Next
}

func sortList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	length := 0
	for node := head; node != nil; node = node.Next {
		length++
	}

	dummyHead := &ListNode{Next: head}
	for subLength := 1; subLength < length; subLength <<= 1 {
		prev, cur := dummyHead, dummyHead.Next
		for cur != nil {
			head1 := cur
			for i := 1; i < subLength && cur.Next != nil; i++ {
				//a <<= 1  : a = a << 1 : a左移1位 等价于 a = a * 2
				cur = cur.Next
			}

			head2 := cur.Next
			cur.Next = nil
			cur = head2
			for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {
				cur = cur.Next
			}

			var next *ListNode
			if cur != nil {
				next = cur.Next
				cur.Next = nil
			}

			prev.Next = merge(head1, head2)

			for prev.Next != nil {
				prev = prev.Next
			}
			cur = next
		}
	}
	return dummyHead.Next
}

func main() {
	l := &ListNode{
		Val: 4,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val:  1,
					Next: nil,
				},
			},
		},
	}
	fmt.Println(sortList(l))
}
